一、GCN [2016]

《Semi-supervised classification with graph convolutional networks》

1. 考虑在 graph（如，引文网络 citation network ）中对节点（如，文档）进行分类的问题，其中仅一小部分节点有 label 信息。这个问题可以被定义为基于图的半监督学习（graph-based semi-supervised learning），其中 label 信息通过某种形式的 explicit graph-based regularization 在图上被平滑（ smoothed ），例如在损失函数中使用图拉普拉斯正则化（graph Laplacian regularization）项：

   $$\begin{array}{c}\mathcal{L}={\mathcal{L}}_0+\lambda \times {\mathcal{L}}_{\text{reg}}\\ {\mathcal{L}}_{\text{reg}}=\sum _{i,j}{A}_{i,j}{\Vert f({\overrightarrow{\mathbf{x}}}_i)-f({\overrightarrow{\mathbf{x}}}_j)\Vert }^2=f(\mathbf{X}{)}^{\mathrm{\top }}\mathrm{\Delta }f(\mathbf{X})\end{array}$$

   其中：

   • 无向图 $\mathcal{G}=(\mathcal{V},\mathcal{E})$$\mathcal G=(\mathcal V,\mathcal E)$ ，$\mathcal{V}$$\mathcal V$ 为节点集合，$\mathcal{E}$$\mathcal E$ 为边集合。节点数量为 $N$$N$ 。

   • $\mathbf{A}\in {\mathbb{R}}^{N\times N}$$\mathbf A\in \mathbb R^{N\times N}$ 为图的邻接矩阵，$\mathbf{D}$$\mathbf D$ 为度矩阵其中 $D_{i,i}=\sum _j{A}_{i,j}$$D_{i,i} = \sum_j A_{i,j}$ ，$\mathrm{\Delta }=\mathbf{D}-\mathbf{A}$$\Delta = \mathbf D- \mathbf A$ 为未归一化的拉普拉斯算子 。

   • ${\mathcal{L}}_0$$\mathcal L_0$ 表示图中有标签部分的监督损失：

     $${\mathcal{L}}_0=\sum _{i\in {\mathcal{Y}}_L}{\Vert f({\overrightarrow{\mathbf{x}}}_i)-y_i\Vert }^2$$

     其中：

     • ${\overrightarrow{\mathbf{x}}}_i\in {\mathbb{R}}^C$$\mathbf{\vec x}_i\in \mathbb R^{C}$ 为节点 $i$$i$ 的输入特征（维度为 $C$$C$ ），$\mathbf{X}\in {\mathbb{R}}^{N\times C}$$\mathbf X\in \mathbb R^{N\times C}$ 为节点的特征向量拼接的矩阵。

     • $y_i$$y_i$ 为节点 $i$$i$ 的标签。${\mathcal{Y}}_L$$\mathcal Y_L$ 为带标签节点的集合。

     • $f(\cdot )\in \mathbb{R}$$f(\cdot)\in \mathbb R$ 是一个类似神经网络的可微函数，它将输入 ${\overrightarrow{\mathbf{x}}}_i$$\mathbf{\vec x}_i$ 映射到类别空间，即 $\hat{y}$$\hat y$。$f(\mathbf{X})\in {\mathbb{R}}^N$$f(\mathbf X)\in \mathbb R^N$ 。

   • ${\mathcal{L}}_{\text{reg}}$$\mathcal L_\text{reg}$ 为正则化项，$\lambda$$\lambda$ 为正则化项系数。

     正则化项的物理意义为：

     • 如果两个节点距离较近（即 $A_{i,j}$$A_{i,j}$ 较大），则它们的预估 label 应该比较相似（即 $f({\overrightarrow{\mathbf{x}}}_i)$$f(\mathbf{\vec x}_i)$ 和 $f({\overrightarrow{\mathbf{x}}}_j)$$f(\mathbf{\vec x}_j)$ 距离相近）。

     • 如果两个节点距离较远（即 $A_{i,j}$$A_{i,j}$ 较小），则它们的预估 label 可以相似也可以不相似。

   因此上述损失函数 $\mathcal{L}$$\mathcal L$ 假设：graph 中相连的节点很可能共享相同的label 。然而，这种假设会限制模型的表达能力，因为图中的边不一定编码节点相似性，边也可能包含其它信息。

   在论文 《Semi-supervised classification with graph convolutional networks》中，作者直接使用神经网络模型 $f(\mathbf{X},\mathbf{A})$$f(\mathbf X,\mathbf A)$ 对图结构进行编码，并对所有带标签的节点在监督目标 ${\mathcal{L}}_0$$\mathcal L_0$ 上进行训练，从而避免在损失函数中进行显式的、基于图的正则化。 $f(\cdot )$$f(\cdot)$ 依赖于图的邻接矩阵 $\mathbf{A}$$\mathbf A$ ，这允许模型从监督损失 ${\mathcal{L}}_0$$\mathcal L_0$ 中分配（distribute）梯度信息，并使得模型能够学习带标签节点的representation 和不带标签节点的 representation。

   论文有两个贡献：

   • 首先，论文为直接在图上运行的神经网络模型引入了一个简单且表现良好的 layer-wise 传播规则（propagation rule），并展示了它是如何从谱图卷积（spectral graph convolution）的一阶近似中启发而来。

   • 其次，论文展示了这种形式的基于图的神经网络模型如何用于对图中节点进行快速且可扩展的半监督分类。对多个数据集的实验表明，论文的模型在分类准确性和效率（以 wall-clock time 衡量）方面与 SOTA 的半监督学习方法相比具有优势。

2. 相关工作：相关工作：我们的模型主要受到 graph-based 半监督学习领域、最近在图上的神经网络等工作的启发。接下来我们简要概述了这两个领域的相关工作。

   • graph-based 半监督学习：近年来人们已经提出了大量使用 graph representation 的半监督学习方法，其中大多数分为两类：使用某种形式的显式的图拉普拉斯正则化方法，以及基于 graph embedding 的方法。

     • 图拉普拉斯正则化的突出例子包括标签传播（ label propagation）、流形正则化 （manifold regularization）、以及深度半监督 embedding 。

     • 最近，人们的注意力已经转移到graph embedding 模型，其中 graph embedding 模型受 skip-gram 模型所启发。

       DeepWalk 通过预测节点的局部邻域（local neighborhood）来学习 embedding，其中局部邻域是通过图上的随机游走采样而来。LINE 和 node2vec 使用更复杂的随机游走方案来扩展了 DeepWalk 。

       然而，对于所有这些方法，都需要一个包含随机游走生成和半监督训练的 multistep pipeline ，其中每个 step 都必须单独优化。Planetoid 通过在学习 embedding 的过程中注入label 信息来缓解这个问题。

   • 图上的神经网络：

     • 《A new model for learning in graph domains》 曾经介绍在图上运行的神经网络。《The graph neural network model》 将图神经网络作为循环神经网络的一种形式。他们的框架需要重复应用收缩映射（ contraction map ）作为传播函数（ propagation function），直到 node representation 达到稳定的不动点（fixed point） 。后来，《Gated graph sequence neural networks》 通过将循环神经网络的现代实践引入到原始图神经网络框架中，从而缓解了这种限制。

     • 《Convolutional networks on graphs for learning molecular fingerprints》 在图上引入了一种类似卷积的传播规则和方法，从而用于 graph-level 分类。他们的方法需要学习 node degree-specific 的权重矩阵，这些权重矩阵无法扩展到具有宽泛（wide）的 node degree 分布的大型图。相反，我们的模型每层使用单个权重矩阵，并通过对邻接矩阵进行适当的归一化从而处理变化的 node degree 。

     • 《Diffusion-convolutional neural networks》 最近引入了 graph-based 神经网络来进行节点分类。他们报告了 $O(N^2)$$O(N^2)$ 的复杂度，这限制了模型的应用范围。《Learning convolutional neural networks for graphs》 引入了一个不同但是相关（related）的模型，他们将图局部（locally）地转换为序列，然后馈入传统的一维卷积神经网络，而这需要在预处理步骤中定义节点排序（node ordering）。

     • 我们的方法基于谱图卷积神经网络（ spectral graph convolutional neural network），该模型在 《Spectral networks and locally connected networks on graphs》 被引入，并由 《Convolutional neural networks on graphs with fast localized spectral filtering》 通过快速局部卷积（fast localized convolution）进行了扩展。

     与这些工作相比，我们在此考虑在大型网络中进行 transductive 的节点分类任务。我们表明，在这种情况下，可以将《Spectral networks and locally connected networks on graphs》 和 《Convolutional neural networks on graphs with fast localized spectral filtering》 的原始框架进行一些简化，从而提高大型网络的可扩展性和分类性能。

1.1 模型

1.1.1 图上卷积的快速近似

1. 这里我们提供本文模型的理论动机。我们考虑具有以下 layer-wise 传播规则的一个多层 Graph Convolutional Network: GCN：

   $${\mathbf{H}}^{(l+1)}=\sigma \left({\tilde{\mathbf{D}}}^{-1/2}\tilde{\mathbf{A}}{\tilde{\mathbf{D}}}^{-1/2}{\mathbf{H}}^{(l)}{\mathbf{\Theta }}^{(l)}\right)$$

   其中：

   • $\tilde{\mathbf{A}}=\mathbf{A}+{\mathbf{I}}_N$$\tilde{\mathbf A} = \mathbf A + \mathbf I_N$ 是带自环的无向图的邻接矩阵，${\mathbf{I}}_N$$\mathbf I_N$ 为单位矩阵，$N$$N$ 为节点数量。$\tilde{\mathbf{D}}$$\tilde {\mathbf D}$ 为带自环的度矩阵，其中 ${\tilde{D}}_{i,i}=\sum _j{\tilde{A}}_{i,j}$$\tilde D_{i,i} = \sum_j \tilde A_{i,j}$ 。

   • ${\mathbf{H}}^{(l)}\in {\mathbb{R}}^{N\times d}$$\mathbf H^{(l)}\in \mathbb R^{N\times d}$ 为第 $l$$l$ 层的激活矩阵，${\mathbf{H}}^0=\mathbf{X}$$\mathbf H^{0} = \mathbf X$ ， $d$$d$ 为特征向量维度。${\mathbf{\Theta }}^{(l)}\in {\mathbb{R}}^{d\times d}$$\mathbf \Theta^{(l)}\in \mathbb R^{d\times d}$ 为第 $l$$l$ 层的权重矩阵。 $\sigma (\cdot )$$\sigma(\cdot)$ 为激活函数。

   接下来我们将展示这种传播规则可以通过图上局部谱滤波器（localized spectral filters）的一阶近似所启发而来。

   上式物理意义：第 $l+1$$l+1$ 层中每个节点的representation 可以这样得到：

   • 首先，将邻域内节点（包含它自身）在第 $l$$l$ 层的representation 进行加权和，加权的权重为边的归一化权重（即 ${\tilde{A}}_{i,j}/{\tilde{D}}_{i,i}$$\tilde A_{i,j}/\tilde D_{i,i}$ ）。

   • 然后，将这个加权和通过一个单层前馈神经网络，网络权重为 ${\mathbf{\Theta }}^{(l)}$$\mathbf\Theta^{(l)}$ 、激活函数为 $\sigma (\cdot )$$\sigma(\cdot)$ 。

a. 谱图卷积

1. 我们考虑图上的谱卷积（spectral convolution），它定义为信号 $\overrightarrow{\mathbf{x}}\in {\mathbb{R}}^N$$\mathbf{\vec x}\in \mathbb R^N$ （该信号由每个节点上的一个标量组成）在傅里叶域与 $\overrightarrow{\theta }\in {\mathbb{R}}^N$$\vec\theta\in \mathbb R^N$ 参数化的滤波器 $g_{\theta }=\text{diag}\left(\overrightarrow{\theta }\right)$$g_\theta=\text{diag}\left(\vec\theta\right)$ 的乘积，即：

   $$g_{\theta }\ast \overrightarrow{\mathbf{x}}=\mathbf{U}{g}_{\theta }{\mathbf{U}}^{\mathrm{\top }}\overrightarrow{\mathbf{x}}$$

   其中：

   • $\mathbf{U}=[{\overrightarrow{\mathbf{u}}}_0,\cdots ,{\overrightarrow{\mathbf{u}}}_{N-1}]\in {\mathbb{R}}^{N\times N}$$\mathbf U=\left[\mathbf{\vec u}_0,\cdots,\mathbf{\vec u}_{N-1}\right]\in \mathbb R^{N\times N}$ 为归一化的图拉普拉斯矩阵 $\mathbf{L}={\mathbf{I}}_N-{\mathbf{D}}^{-1/2}\mathbf{A}{\mathbf{D}}^{-1/2}$$\mathbf L = \mathbf I_N - \mathbf D^{-1/2}\mathbf A\mathbf D^{-1/2}$ 的特征向量 ${\overrightarrow{\mathbf{u}}}_i$$\mathbf{\vec u}_i$ 组成（按列组成）。$\mathbf{L}=\mathbf{U}\mathbf{\Lambda }{\mathbf{U}}^{\mathrm{\top }}$$\mathbf L = \mathbf U\mathbf\Lambda \mathbf U^\top$ ，$\mathbf{\Lambda }=\text{diag}([{\lambda }_0,\cdots ,{\lambda }_{N-1}])$$\mathbf\Lambda=\text{diag}([\lambda_0,\cdots,\lambda_{N-1}])$ 为特征值 ${\lambda }_i$$\lambda_i$组成的对角矩阵。

   • 对于信号 $\overrightarrow{\mathbf{x}}$$\mathbf{\vec x}$，$\widehat{\overrightarrow{\mathbf{x}}}={\mathbf{U}}^{\mathrm{\top }}\overrightarrow{\mathbf{x}}$$\hat{\mathbf{\vec x}} = \mathbf U^\top \mathbf{\vec x}$ 表示信号的图傅里叶变换（ graph Fourier transform）。$\overrightarrow{\mathbf{x}}=\mathbf{U}\widehat{\overrightarrow{\mathbf{x}}}$$\mathbf{\vec x}=\mathbf U\hat{\mathbf{\vec x}}$ 表示图傅里叶逆变换。

     注意，这里的信号 $\overrightarrow{\mathbf{x}}\in {\mathbb{R}}^N$$\mathbf{\vec x}\in \mathbb R^N$ 是定义在整个图的所有节点上，而前面定义的节点特征 ${\overrightarrow{\mathbf{x}}}_i\in {\mathbb{R}}^C$$\mathbf{\vec x}_i\in \mathbb R^{C}$ 是定义在单个节点 $i$$i$ 上。我们有：

     $$\begin{array}{c}\mathbf{X}={[{\overrightarrow{\mathbf{x}}}_1,\cdots ,{\overrightarrow{\mathbf{x}}}_N]}^{\mathrm{\top }}=\left[\begin{array}{cccc}{x}_{1,1}& x_{1,2}& \cdots & x_{1,C}\\ x_{2,1}& x_{2,2}& \cdots & x_{2,C}\\ ⋮& ⋮& \ddots & ⋮\\ x_{N,1}& x_{N,2}& \cdots & x_{N,d_N}\end{array}\right]\end{array}$$

     则 $\mathbf{X}$$\mathbf X$ 有两种解读方式：

     • 按行解读：第 $i$$i$ 行代表节点 $i$$i$ 的 $C$$C$ 为特征，$1\le i\le N$$1\le i\le N$ 。

     • 按列解读：第 $j$$j$ 列代表定义在图上的第 $j$$j$ 个信号，$1\le j\le C$$1\le j\le C$ 。

   • 我们可以将 $g_{\theta }$$g_\theta$ 理解为 $\mathbf{L}$$\mathbf L$ 特征值的函数，即 $g_{\theta }(\mathbf{\Lambda })$$g_\theta(\mathbf\Lambda)$ 。

2. 计算 $g_{\theta }\ast \overrightarrow{\mathbf{x}}$$g_\theta*\mathbf{\vec x}$ 的计算量很大，因为与矩阵 $\mathbf{U}$$\mathbf U$ 的乘法是 $O(N^2)$$O(N^2)$ 。此外，对于大型图，首先计算 $\mathbf{L}$$\mathbf L$ 的特征分解可能会非常昂贵。为了解决这个问题，《Aavelets on graphs via spectral graph theory》 等人提出，$g_{\theta }(\mathbf{\Lambda })$$g_\theta(\mathbf\Lambda)$ 可以通过切比雪夫多项式 $T_k(x)$$T_k(x)$ 的截断展开（ truncated expansion）（$K$$K$ 阶）来很好地近似：

   $$g_{{\theta }^{\prime }}(\mathbf{\Lambda })\simeq \sum _{k=0}^K{\theta }_k^{\prime }{T}_k\left(\tilde{\mathbf{\Lambda }}\right)$$

   其中：

   • $\tilde{\mathbf{\Lambda }}=\frac{2}{{\lambda }_{max}}\mathbf{\Lambda }-{\mathbf{I}}_N$$\tilde{\mathbf\Lambda} = \frac{2}{\lambda_\max}\mathbf\Lambda - \mathbf I_N$ 为缩放的特征值矩阵（使得缩放之后的取值在 [-1,+1] 之间），${\lambda }_{max}$$\lambda_\max$ 为 $\mathbf{L}$$\mathbf L$ 最大的特征值。

   • ${\overrightarrow{\theta }}^{\prime }=({\theta }_0^{\prime },{\theta }_1^{\prime },{\theta }_2^{\prime },\cdots ,{\theta }_K^{\prime })\in {\mathbb{R}}^{K+1}$$\vec\theta^\prime=\left(\theta^\prime_0,\theta^\prime_1,\theta^\prime_2,\cdots,\theta^\prime_K\right) \in \mathbb R^{K+1}$ 为切比雪夫多项式系数。

   • $T_k(x)$$T_k(x)$ 为 $k$$k$ 阶切比雪夫多项式，它递归地定义为：

     $$\begin{array}{c}{T}_0(x)=1,T_1(x)=x\\ T_k(x)=2x{T}_{k-1}(x)-T_{k-2}(x)\end{array}$$

   回到我们对信号 $\overrightarrow{\mathbf{x}}$$\mathbf{\vec x}$ 关于滤波器 $g_{{\theta }^{\prime }}$$g_{\theta^\prime}$ 的卷积的定义，则我们有：

   $$g_{{\theta }^{\prime }}\ast \overrightarrow{\mathbf{x}}\simeq \sum _{k=0}^K{\theta }_k^{\prime }{T}_k\left(\tilde{\mathbf{L}}\right)\overrightarrow{\mathbf{x}}$$

   其中：$\tilde{\mathbf{L}}=\frac{2}{{\lambda }_{max}}\mathbf{L}-{\mathbf{I}}_N$$\tilde{\mathbf L} = \frac{2}{\lambda_\max}\mathbf L - \mathbf I_N$ 为缩放后的拉普拉斯矩阵。

   上式成立是因为我们很容易证明：${\left(\mathbf{U}\mathbf{\Lambda }{\mathbf{U}}^{\mathrm{\top }}\right)}^k=\mathbf{U}{\mathbf{\Lambda }}^k{\mathbf{U}}^{\mathrm{\top }}$$\left(\mathbf U\mathbf\Lambda\mathbf U^\top\right)^k = \mathbf U\mathbf\Lambda^k\mathbf U^\top$ 。

   注意，这个表达式现在是 $K$$K$ 阶局部化 （K-localized ）的，因为它是拉普拉斯矩阵的 $K$$K$ 阶多项式，即它的结果仅依赖于距离中心节点最大 K step 的节点（即，$K$$K$ 阶邻域）。

   $g_{{\theta }^{\prime }}\ast \overrightarrow{\mathbf{x}}$$g_{\theta^\prime} * \mathbf{\vec x}$的复杂度是 $O(|\mathcal{E}|)$$O(|\mathcal E|)$ 的，即与边的数量呈线性关系。《Convolutional neural networks on graphs with fast localized spectral filtering》 使用这种 K-localized 卷积来定义图上的卷积神经网络。

1.1.2 Layer-wise 线性模型

1. 可以通过堆叠多个 $g_{{\theta }^{\prime }}\ast \overrightarrow{\mathbf{x}}$$g_{\theta^\prime} * \mathbf{\vec x}$ 形式的卷积层从而构建基于图卷积的神经网络模型，每个 layer 后跟随一个 point-wise non-linearity 。现在，假设我们将 layer-wise 卷积操作限制为 $K=1$$K=1$ ，即一个关于 $\mathbf{L}$$\mathbf L$ 的线性函数。

   通过这种方式，我们仍然可以通过堆叠多个这种 layer 来恢复（ recover ）丰富类型的卷积滤波器函数，但是我们不限于由诸如切比雪夫多项式给出的显式参数化。对于具有非常宽泛（ wide ）的node degree 分布的图（如社交网络、引文网络、知识图谱、以及许多现实世界其它的图数据集），我们直观地期望这样的模型可以缓解图的局部邻域结构（local neighborhood structure）的过拟合问题。此外，对于固定的计算预算（computational budget），这种 layer-wise 线性公式允许我们构建更深的模型。众所周知，更深的模型在很多领域可以提高模型容量。

2. 在 GCN 的这个线性公式中，我们进一步近似 ${\lambda }_{max}=2$$\lambda_\max = 2$ ，因为我们可以预期神经网络参数将在训练期间适应这种 scale 的变化。

   为什么选择 ${\lambda }_{max}$$\lambda_\max$ 近似为 2 ？因为原始公式中有系数 $\frac{2}{{\lambda }_{max}}$$\frac{2}{\lambda_\max}$ 。

   在这些近似下，$g_{{\theta }^{\prime }}\ast \overrightarrow{\mathbf{x}}$$g_{\theta^\prime} * \mathbf{\vec x}$ 简化为：

   $$g_{{\theta }^{\prime }}\ast \overrightarrow{\mathbf{x}}\simeq {\theta }_0^{\prime }\overrightarrow{\mathbf{x}}+{\theta }_1^{\prime }(\mathbf{L}-{\mathbf{I}}_N)\overrightarrow{\mathbf{x}}={\theta }_0^{\prime }\overrightarrow{\mathbf{x}}-{\theta }_1^{\prime }{\mathbf{D}}^{-1/2}\mathbf{A}{\mathbf{D}}^{-1/2}\overrightarrow{\mathbf{x}}$$

   它包含两个自由参数（ free parameter ）${\theta }_0^{\prime },{\theta }_1^{\prime }$$\theta_0^\prime,\theta_1^\prime$ 。滤波器参数 ${\theta }_0^{\prime },{\theta }_1^{\prime }$$\theta_0^\prime,\theta_1^\prime$ 可以在整个图上共享。这种形式的滤波器的连续应用（ successive application ）可以有效地对节点的 $k$$k$ 阶邻域进行卷积，其中 $k$$k$ 为神经网络模型中卷积层的数量。

   在实践中，进一步限制参数的数量从而解决过拟合问题、并最小化每层的操作数量（如矩阵乘法）可能是有益的。因此我们进一步简化，令 $\theta ={\theta }_0^{\prime }=-{\theta }_1^{\prime }$$\theta = \theta_0^\prime = -\theta_1^\prime$ ，现在只有一个参数：

   $$g_{{\theta }^{\prime }}\ast \overrightarrow{\mathbf{x}}\simeq \theta ({\mathbf{I}}_N+{\mathbf{D}}^{-1/2}\mathbf{A}{\mathbf{D}}^{-1/2})\overrightarrow{\mathbf{x}}$$

   为什么要凑成这个形式？假设 $\theta =\frac{1}{\beta }{\theta }_0^{\prime }=-{\theta }_1^{\prime }$$\theta=\frac{1}{\beta}\theta_0^\prime = -\theta_1^\prime$ ，其中 $\beta \ne 0$$\beta\ne 0$ 为超参数。则有：

   $$g_{{\theta }^{\prime }}\ast \overrightarrow{\mathbf{x}}\simeq \theta (\beta {\mathbf{I}}_N+{\mathbf{D}}^{-1/2}\mathbf{A}{\mathbf{D}}^{-1/2})\overrightarrow{\mathbf{x}}$$

   则根据renormalization 技巧，我们有：$\tilde{\mathbf{A}}=\mathbf{A}+\beta {\mathbf{I}}_N$$\tilde{\mathbf A}=\mathbf A + \beta\mathbf I_N$ 。则参数 $\beta$$\beta$ 平衡了邻域链接（由 $\mathbf{A}$$\mathbf A$ 刻画）和自链接（由 ${\mathbf{I}}_N$$\mathbf I_N$ 刻画）之间的重要性。$\beta$$\beta$ 既可以作为模型参数来从数据中学习，也可以作为超参数由验证集调优得到。

   注意，${\mathbf{I}}_N+{\mathbf{D}}^{-1/2}\mathbf{A}{\mathbf{D}}^{-1/2}$$\mathbf I_N + \mathbf D^{-1/2}\mathbf A \mathbf D^{-1/2}$ 的特征值的取值范围是 [0, 2] 。因此，当在深度神经网络模型中重复应用该算子时，会导致数值不稳定和梯度爆炸/消失。为了缓解这个问题，我们引入以下 renormalization 技巧：

   $$\begin{array}{c}{\mathbf{I}}_N+{\mathbf{D}}^{-1/2}\mathbf{A}{\mathbf{D}}^{-1/2}\to {\tilde{\mathbf{D}}}^{-1/2}\tilde{\mathbf{A}}{\tilde{\mathbf{D}}}^{-1/2}\\ \tilde{\mathbf{A}}=\mathbf{A}+{\mathbf{I}}_N,{\tilde{D}}_{i,i}=\sum _j{\tilde{A}}_{i,j}\end{array}$$

   我们可以将这个定义推广到具有 $C$$C$ 个输入通道的信号 $\mathbf{X}\in {\mathbb{R}}^{N\times C}$$\mathbf X\in \mathbb R^{N\times C}$（即每个节点的 $C$$C$ 维特征向量）和 $F$$F$ 个滤波器（或 feature map）：

   $$\mathbf{Z}={\tilde{\mathbf{D}}}^{-1/2}\tilde{\mathbf{A}}{\tilde{\mathbf{D}}}^{-1/2}\mathbf{X}\mathbf{\Theta }$$

   其中：

   • $\mathbf{\Theta }\in {\mathbb{R}}^{C\times F}$$\mathbf \Theta\in \mathbb R^{C\times F}$ 为滤波器参数组成的矩阵。

   • $\mathbf{Z}\in {\mathbb{R}}^{N\times F}$$\mathbf Z\in \mathbb R^{N\times F}$ 为卷积后的 signal matrix 。

   该卷积操作的计算复杂度为 $O(|\mathcal{E}|FC)$$O(|\mathcal E|FC)$，因为 $\tilde{\mathbf{A}}\mathbf{X}$$\tilde{\mathbf A} \mathbf X$ 可以有效地实现为稀疏矩阵与稠密矩阵的乘积。

1.2 半监督节点分类

1. 引入了一个简单而灵活的模型 $f(\mathbf{X},\mathbf{A})$$f(\mathbf X,\mathbf A)$ 从而在图上进行有效的信息传播之后，我们可以回到半监督节点分类问题。如引言部分所介绍，我们可以通过在数据 $\mathbf{X}$$\mathbf X$ 和底层图结构的邻接矩阵 $\mathbf{A}$$\mathbf A$ 上调整我们的模型 $f(\mathbf{X},\mathbf{A})$$f(\mathbf X,\mathbf A)$ 来放松某些假设，这些假设常用于 graph-based 半监督学习。我们希望该 setting 在邻接矩阵 $\mathbf{A}$$\mathbf A$ 包含数据 $\mathbf{X}$$\mathbf X$ 中不存在的信息的情况下特别强大，例如引文网络中文档之间的引用链接（citation link）、或者知识图谱中的关系（relation ）。整个模型是一个用于半监督学习的多层 GCN，如下图所示。

   

2. 接下来我们考虑在具有对称的邻接矩阵 $\mathbf{A}$$\mathbf A$ 的图上用于半监督节点分类的两层 GCN 。我们首先在预处理步骤中计算 ：

   $$\hat{\mathbf{A}}={\tilde{\mathbf{D}}}^{-1/2}\tilde{\mathbf{A}}{\tilde{\mathbf{D}}}^{-1/2}$$

   然后我们的前向计算采用简单的形式：

   $$\mathbf{Z}=f(\mathbf{X},\mathbf{A})=\text{softmax}\left(\hat{\mathbf{A}}\text{relu}\left(\hat{\mathbf{A}}\mathbf{X}{\mathbf{\Theta }}^{(0)}\right){\mathbf{\Theta }}^{(1)}\right)$$

   其中：

   • ${\mathbf{\Theta }}^{(0)}\in {\mathbb{R}}^{C\times H}$$\mathbf \Theta^{(0)}\in \mathbb R^{C\times H}$ 为具有 $H$$H$ 个feature map 隐层的 input-to-hidden 的权重矩阵，${\mathbf{\Theta }}^{(1)}\in {\mathbb{R}}^{H\times F}$$\mathbf \Theta^{(1)}\in \mathbb R^{H\times F}$ 为 hidden-to-output 的权重矩阵。

   • softmax 激活函数定义为：$\text{softmax}(x_i)=\frac{\exp (x_i)}{\sum _j\exp (x_j)}$$\text{softmax}(x_i) = \frac{\exp(x_i)}{\sum_j\exp(x_j)}$ 。

   对于半监督多类分类，我们评估所有标记节点的交叉熵：

   $$\mathcal{L}=-\sum _{l\in {\mathcal{Y}}_L}\sum _{f=1}^F{Y}_{l,f}\ln (Z_{l,f})$$

   其中：${\mathcal{Y}}_l$$\mathcal Y_l$ 为具有 label 的节点索引集合。

   神经网络权重 ${\mathbf{\Theta }}^{(0)}$$\mathbf \Theta^{(0)}$ 和 ${\mathbf{\Theta }}^{(1)}$$\mathbf \Theta^{(1)}$ 是通过梯度下降来训练的。在这项工作中，我们每次训练迭代使用完整数据集执行 batch gradient descent 。只要数据集能够适合 （fit ）内存，这就是一个可行的选择。当邻接矩阵 $\mathbf{A}$$\mathbf A$ 是稀疏的时候，内存需求是 $O(|\mathcal{E}|)$$O(|\mathcal E|)$ ，即与边的数量呈线性关系。我们在训练过程中通过 dropout 引入随机性。我们将 mini-batch 随机梯度下降这个 memory-efficient 扩展留待未来工作。

3. 在实践中，我们采用 TensorFlow 使用 sparse-dense 矩阵乘法来高效地基于 GPU 实现 $\mathbf{Z}=f(\mathbf{X},\mathbf{A})$$\mathbf Z = f(\mathbf X,\mathbf A)$ ，其计算复杂度为 $O(|\mathcal{E}|CHF)$$O(|\mathcal E|CHF)$ ，即与边的数量呈线性关系。

1.3 和 WL 算法的关系

1.3.1 WL 算法

1. 理想情况下图神经网络模型应该能够学到图中节点的representation，该representation 必须能够同时考虑图的结构和节点的特征。

   一维 Weisfeiler-Lehman:WL-1 算法提供了一个研究框架。给定图以及初始节点标签，该框架可以对节点标签进行唯一分配（unique assignment）。

   注意，这里的“标签”不仅包括节点上的监督 label 信号，也包括节点上的属性信息。

2. WL-1 算法：令 $h_i^{(t)}$$h_i^{(t)}$ 为节点 $v_i$$v_i$ 在第 $t$$t$ 轮分配的标签，${\mathcal{N}}_i$$\mathcal N_i$ 为节点 $v_i$$v_i$ 的邻域节点集合，$\text{hash}(\cdot )$$\text{hash}(\cdot)$ 为一个哈希函数。

   • 输入：初始节点标签 $\{h_1^{(0)},h_2^{(0)},\cdots ,h_N^{(0)}\}$$\left\{h_1^{(0)},h_2^{(0)},\cdots,h_N^{(0)}\right\}$

   • 输出：最终节点标签 $\{h_1^{(T)},h_2^{(T)},\cdots ,h_N^{(T)}\}$$\left\{h_1^{(T)},h_2^{(T)},\cdots,h_N^{(T)}\right\}$

   • 算法步骤：

     • 初始化 $t=0$$t=0$ 。

     • 迭代直到 $t=T$$t=T$ 或者节点的标签到达稳定状态。迭代步骤为：

       • 循环遍历 $v_i\in \mathcal{V}$$v_i\in \mathcal V$，执行：

         $$h_i^{(t+1)}=\text{hash}\left(\sum _{j\in {\mathcal{N}}_i}{h}_j^{(t)}\right)$$

       • $t=t+1$$t = t+1$

     • 返回每个节点的标签。

3. 如果我们采用一个神经网络来代替 hash 函数，同时假设 $h_i$$h_i$ 为向量，则有：

   $${\overrightarrow{\mathbf{h}}}_i^{(l+1)}=\sigma \left(\sum _{j\in {\mathcal{N}}_i}\frac{1}{c_{i,j}}{\mathbf{\Theta }}^{(l{)}^{\mathrm{\top }}}{\overrightarrow{\mathbf{h}}}_j^{(l)}\right)$$

   其中：${\overrightarrow{\mathbf{h}}}_i^{(l)}$$\mathbf{\vec h}_i^{(l)}$ 为第 $l$$l$ 层神经网络中节点 $i$$i$ 的激活向量 （ vector of activations ）；${\mathbf{\Theta }}^{(l)}$$\mathbf \Theta^{(l)}$ 为第 $l$$l$ 层的权重矩阵；$\sigma (\cdot )$$\sigma(\cdot)$ 为非线性激活函数。$c_{i,j}$$c_{i,j}$ 为针对边 $(v_i,v_j)$$(v_i,v_j)$ 的正则化常数。

   我们定义 $c_{i,j}=\sqrt{D_i{D}_j}$$c_{i,j} = \sqrt{D_iD_j}$ ，其中 $D_i=|{\mathcal{N}}_i|$$D_i = |\mathcal N_i|$ 为节点$v_i$$v_i$ 的度（degree），则上式等价于我们 GCN 模型的传播规则。因此我们可以将 GCN 模型解释为图上 WL-1 算法的微分化（differentiable）的和参数化（parameterized）的推广。

1.3.2 随机权重的 node embedding

1. 通过与 WL-1 算法的类比，我们可以认为：即使是未经训练的、具有随机权重的 GCN 模型也可以充当图中节点的一个强大的特征提取器。如：考虑下面的一个三层GCN 模型：

   $$\mathbf{Z}=\tanh (\hat{\mathbf{A}}\tanh (\hat{\mathbf{A}}\tanh \left(\hat{\mathbf{A}}\mathbf{X}{\mathbf{\Theta }}^{(0)}\right){\mathbf{\Theta }}^{(1)}){\mathbf{\Theta }}^{(2)})$$

   其中权重矩阵是通过 Xavier 初始化的：${\mathbf{\Theta }}^{(k)}\sim \text{Uniform}[-\sqrt{\frac{6}{h_k+h_{k+1}}},\sqrt{\frac{6}{h_k+h_{k+1}}}]$$\mathbf \Theta^{(k)}\sim \text{Uniform}\left[-\sqrt{\frac{6}{h_k+h_{k+1}}},\sqrt{\frac{6}{h_k+h_{k+1}}}\right]$ 。

   我们将这个三层 GCN 模型应用于 Zachary 的 karate club network ，该网络包含34个节点、154 条边。每个节点都属于一个类别，一共四种类别。节点的类别是通过 modularity-based 聚类算法进行标注的。如下图所示，颜色表示节点类别。

   

   我们令 $\mathbf{X}={\mathbf{I}}_N$$\mathbf X = \mathbf I_N$，即每个节点除了节点ID 之外不包含任何其它特征。另外节点的ID 是随机分配的，也不包含任何信息。我们选择隐层的维度为4、输出层的维度为2 ，因此输出层的输出 $\mathbf{Y}$$\mathbf Y$ 能够直接视为二维数据点来可视化。

   下图给出了未经训练的 GCN 模型（即前向传播）获得的node embedding，这些结果与从DeepWalk 获得的node embedding 效果相当，而DeepWalk 使用了代价更高的无监督训练过程。

   因此可以将随机初始化的 GCN 作为 graph embedding 特征抽取器来使用，而且还不用训练。

   

1.3.3 半监督 node embedding

1. 在karate club network数据集上，我们观察半监督分类任务期间 node embedding 如何变化。这种可视化效果提供了关于 GCN 模型如何利用图结构从而学到对于分类任务有益的node embedding 。

   训练配置：

   • 在上述三层GCN 之后添加一个 softmax 输出层，输出节点属于各类别的概率。

   • 每个类别仅使用一个带标签的节点进行训练，一共有四个带标签的节点。

   • 使用Adam 优化器，初始化学习率为 0.01。采用交叉熵损失函数。迭代 300 个 step。

   下图给出多轮迭代中，node embedding 的演变。图中的灰色直线表示图的边，高亮节点（灰色轮廓）表示标记节点。可以看到：模型最终基于图结构以及最少的监督信息，成功线性地分离出了簇团。

   

1.4 实验

1. 我们在多个任务中验证模型性能：在引文网络中进行半监督文档分类、在从知识图谱抽取的二部图中进行半监督实体分类。然后我们评估图的各种传播模型，并对随机图的rum-time进行分析。

2. 数据集：

   • 引文网络数据集：我们考虑 Citeseer,Cora,Pubmed 三个引文网络数据集，每个数据集包含以文档的稀疏 bag-of-word: BOW 特征向量作为节点，文档之间的引文链接作为边。我们将引文链接视为无向边，并构造一个二元的对称邻接矩阵 $\mathbf{A}$$\mathbf A$。

     每个文档都有一个类别标签，每个类别仅包含 20个标记节点作为训练样本。

   • NELL 数据集：该数据集是从《Toward an architecture for never-ending language learning》 引入的知识图谱中抽取的数据集。知识图谱是一组采用有向的、带标记的边链接的实体。我们为每个实体对 $(e_1,r,e_2)$$(e_1,r,e_2)$ 分配节点 $\{e_1,e_2,r_1,r_2\}$$\{e_1,e_2,r_1,r_2\}$ ，以及边 $(e_1,r_1)$$(e_1,r_1)$ 和 $(e_2,r_2)$$(e_2,r_2)$ 。其中， $r_1,r_2$$r_1,r_2$ 是知识图谱链接 $r$$r$ 得到的两个“拷贝”的关系节点（relation node），它们之间不存在边。最终我们得到 55864 个关系节点和 9891 个实体节点。

     实体节点（entity node ）通过稀疏的特征向量来描述。我们为每个关系节点分配唯一的 one-hot 向量从而扩展 NELL 的实体特征向量，从而使得每个节点的特征向量为 61278 维稀疏向量。

     对于节点 $i$$i$ 和 $j$$j$ ，如果它们之间存在一条边或者多条边，则设置 $A_{i,j}=1$$A_{i,j} = 1$ 从而构建一个二元对称邻接矩阵。

     在节点的半监督分类任务中，我们为每个类别标记一个节点作为训练集，因此属于非常极端的情况。

   • 随机图：我们生成各种规模的随机Graph 数据集，从而评估每个epoch 的训练时间。

     对于具有 $N$$N$ 个节点的图，我们创建一个随机图：

     • 随机均匀分配 $2N$$2N$ 条边。

     • 令 $\mathbf{X}={\mathbf{I}}_N$$\mathbf X = \mathbf I_N$ ，即每个节点除了其 id 之外没有任何特征，且节点 id 是随机分配的。

     • 每个节点标签为 $y_i=1$$y_i=1$ 。

   各数据集的整体统计如下表所示。标记率（label rate）：表示监督的标记节点数量占总的节点数量的比例。

   

3. 模型设置：除非另有说明，否则我们的 GCN 模型就是前面描述的两层 GCN 模型。

   • 我们将数据集拆分为labled 数据、unlabled 数据、测试数据。其中我们在labled 数据和 unlabled 数据上学习，在测试数据上测试。我们选择测试数据包含 1000 个节点。

     注意，训练期间模型能够“看到”所有节点，但是无法知道测试节点的 label 信息。

     另外我们还使用额外的 500 个带标签的节点作为验证集，用于超参数优化。这些超参数包括：所有层的 dropout rate 、第一个 GCN 层的 $L_2$$L_2$ 正则化系数、隐层的维度。

     注意：验证集的标签不用于训练。

   • 对于引文网络数据集，我们仅在Cora 数据集上优化超参数，并对Citeseer 和 Pubmed 数据集采用相同的超参数。

   • 所有模型都使用 Adam 优化器，初始化学习率为 0.01 。

   • 所有模型都使用早停策略，早停的 epoch 窗口为 10。即：如果连续 10 个 epoch 的验证损失没有下降，则停止继续训练。所有模型最多训练 200 个 epoch 。

   • 我们使用 Xavier 初始化策略：${\mathbf{\Theta }}^{(k)}\sim \text{Uniform}[-\sqrt{\frac{6}{h_k+h_{k+1}}},\sqrt{\frac{6}{h_k+h_{k+1}}}]$$\mathbf \Theta^{(k)}\sim \text{Uniform}\left[-\sqrt{\frac{6}{h_k+h_{k+1}}},\sqrt{\frac{6}{h_k+h_{k+1}}}\right]$ 。

   • 我们对输入的特征向量进行按行的归一化（ row-normalize ）（即每个样本输入特征向量归一化为范数为 1 ）。

   • 在随机图数据集上，我们选择隐层维度为 32，并省略正则化：既不进行dropout，也不进行 $L_2$$L_2$ 正则化。

4. Baseline 模型：我们比较了《Revisiting semi-supervised learning with graph embeddings》 相同的 baseline 方法，即：标签传播算法（label propagation: LP）、半监督embedding 算法（ semi-supervised embedding: SemiEmb ）、流形正则化算法（manifold regularization: MainReg） 、基于skip-gram 的图嵌入算法DeepWalk 。我们忽略了 TSVM 算法，因为它无法扩展到类别数很大的数据集。

   我们进一步与 《Link-based classification》 中提出的iterative classification algorithm: ICA 进行比较。我们还还比较了Planetoid 算法， 我们总是选择他们表现最好的模型变体（transductive vs inductive ）作为 baseline 。

5. 模型比较结果如下表所示。对于ICA ，我们随机运行 100 次、每次以随机的节点顺序训练得到的平均准确率。 所有其它基准模型的结果均来自于 Planetoid 论文，Planetoid* 表示论文中提出的针对每个数据集的最佳变体。

   我们在与《Revisiting semi-supervised learning with graph embeddings》 相同的数据集拆分上训练和测试了我们的模型，并报告随机权重初始化的 100 次的平均准确率（括号中为平均训练时间）。我们为 Citeseer,Cora,Pubmed 使用的超参数为：dropout rate = 0.5、$L_2$$L_2$ 正则化系数为 $5\times {10}^{-4}$$5\times 10^{-4}$、隐层的维度为16 ；为 NELL 使用的超参数为：dropout rate = 0.1，$L_2$$L_2$ 正则化系数为 $1\times {10}^{-5}$$1\times 10^{-5}$，隐层维度为 64 。

   最后我们报告了10 次随机拆分数据集，每次拆分的labled 数据、unlabled 数据、测试数据比例与之前相同，然后给出GCN 的平均准确率和标准差（以百分比表示），记作 GCN(rand. splits) 。

   前面七行是针对同一种数据集拆分，最后一行是不同的数据集拆分。

   

6. 我们在引文网络数据集上比较了我们提出的逐层传播模型的不同变体，实验配置和之前相同，结果如下表所示。

   我们原始的 GCN 模型应用了 renormalization 技巧（粗体），即：

   $$\mathbf{I}+{\mathbf{D}}^{-1/2}\mathbf{A}{\mathbf{D}}^{-1/2}\to {\tilde{\mathbf{D}}}^{-1/2}\tilde{\mathbf{A}}{\tilde{\mathbf{D}}}^{-1/2}$$

   其它的GCN 变体采用Propagation model 字段对应的传播模型。

   • 对于每一种变体模型，我们给出执行100次、每次都是随机权重初始化的平均分类准确率。

   • 对于每层有多个权重 ${\mathbf{\Theta }}_k$$\mathbf{\mathbf \Theta}_k$ 的情况下（如 Chebyshev filter, 1st-order model），我们对第一层的所有权重执行 $L_2$$L_2$ 正则化。

   

7. 我们在随机图上报告了 100 个 epoch 的每个 epoch 平均训练时间。我们在 Tensorflow 上比较了 CPU 和 GPU 实现的结果，其中 * 表示内存溢出错误（Out Of Memory Error ）。

   

8. 最后我们考虑模型的深度对于性能的影响。这里我们报告对 Cora,Citeseer,Pubmed 数据集进行5 折交叉验证的结果。

   除了标准的 GCN 模型之外，我们还报告了模型的一种变体：隐层之间使用了残差连接：

   $${\mathbf{H}}^{(l+1)}=\sigma \left({\tilde{\mathbf{D}}}^{-1/2}\tilde{\mathbf{A}}{\tilde{\mathbf{D}}}^{-1/2}{\mathbf{H}}^{(l)}{\mathbf{\Theta }}^{(l)}\right)+{\mathbf{H}}^{(l)}$$

   在5 折交叉验证的每个拆分中，我们训练400 个 epoch 并且不使用早停策略。我们使用Adam 优化器，初始学习率为 0.01。我们对第一层和最后一层使用dropout rate = 0.5 ，第一层权重执行正则化系数为 $5\times {10}^{-4}$$5\times 10^{-4}$ 的 $L_2$$L_2$ 正则化。GCN 的隐层维度选择为 16 。

   结果如下图所示，其中标记点表示5 折交叉验证的平均准确率，阴影部分表示方差。

   可以看到：

   • 当使用两层或三层模型时，GCN 可以获得最佳效果。

   • 当模型的深度超过七层时，如果不使用残差连接则训练会变得非常困难，表现为训练准确率骤降。因为每个节点的有效上下文会随着层深的增加而扩大。

   • 当模型深度增加时，模型的参数数量也会增加，此时模型的过拟合可能会成为问题。

   

1.5 讨论

1. 半监督模型：在这里展示的实验中，我们的半监督节点分类方法明显优于最近的相关方法。

   • 基于图拉普拉斯正则化的方法很可能受到限制，因为它们假设边仅仅编码了节点的相似性。

   • 另一方面，基于 skip-gram 的方法受限于它们难以优化的 multi-step pipeline 这一事实。

   • 我们提出的模型可以克服这两个限制，同时在效率（以 wall-clock time 衡量）方面仍然优于相关方法。与仅聚合label信息的 ICA 等方法相比，在每一层中从相邻节点传播feature信息提高了分类性能。

   • 我们进一步证明，与使用切比雪夫多项式的朴素的一阶模型 ${\theta }_0^{\prime }\overrightarrow{\mathbf{x}}-{\theta }_1^{\prime }{\mathbf{D}}^{-1/2}\mathbf{A}{\mathbf{D}}^{-1/2}\overrightarrow{\mathbf{x}}$$\theta_0^\prime \mathbf{\vec x} - \theta_1^\prime \mathbf D^{-1/2}\mathbf A \mathbf D^{-1/2}\mathbf{\vec x}$ 或更高阶的图卷积模型 $\sum _{k=0}^K{\theta }_k^{\prime }{T}_k\left(\tilde{\mathbf{L}}\right)\overrightarrow{\mathbf{x}}$$\sum_{k=0}^K \theta_k^\prime T_k\left(\tilde{\mathbf L}\right) \mathbf{\vec x}$ 相比，所提出的重整化的传播模型等式 ${\tilde{\mathbf{D}}}^{-1/2}\tilde{\mathbf{A}}{\tilde{\mathbf{D}}}^{-1/2}\mathbf{X}\mathbf{\Theta }$$\tilde{\mathbf D}^{-1/2}\tilde{\mathbf A}\tilde{\mathbf D}^{-1/2}\mathbf X \mathbf\Theta$ 在许多数据集上提供了更高的效率（更少的参数和操作，如乘法操作或加法操作）以及更好的预测性能。

2. 局限性和未来方向：我们的 Semi-GCN 模型存在一些局限，我们计划在将来克服这些局限性。

   • 内存需求局限性：在full-batch 梯度下降算法中，内存需求随着数据集的大小线性增长。

     • 一种解决方式是：采用 CPU 训练来代替 GPU 训练。这种方式我们在实验中得到验证。

     • 另一种解决方式是：采用 mini-batch 随机梯度下降算法。

       但是mini-batch 随机梯度下降算法必须考虑 GCN 模型的层数。因为对于一个 $K$$K$ 层的 GCN 模型，其 $K$$K$ 阶邻域必须全部存储在内存中。对于节点数量庞大、节点链接很密集的图，这可能需要进一步的优化。

   • 边类型的局限性：目前我们的模型不支持边的特征，也不支持有向图。

     通过NELL 数据集的实验结果表明：可以通过将原始的有向图转化为无向二部图来处理有向图以及边的特征。这通过额外的、代表原始图中的边的节点来实现。

   • 假设的局限性：我们的模型有两个基本假设：

     • 假设 $K$$K$ 层GCN 依赖于 $K$$K$ 阶邻居，即模型的局部性locality。

     • 假设自链接和邻居链接同样重要。

       在某些数据集中，我们可以引入一个折衷（trade-off）：$\tilde{\mathbf{A}}=\mathbf{A}+\beta {\mathbf{I}}_N$$\tilde{\mathbf A} = \mathbf A + \beta \mathbf I_N$ 。其中参数 $\beta$$\beta$

       平衡了自链接和邻居链接的重要性，它可以通过梯度下降来学习（也可以作为超参数来调优）。